Retailers make their money by selling products and therefore seek to maximize the value and volume of products that they sell. Traditionally, retailers attempt to improve product sales by changing the products that they offer in response to recent sales figures, anticipated seasonal trends, industry sales figures, etc. Some retailers with multiple locations further optimize their product mix by considering local and regional data. Many of these changes are done by humans in a piecemeal manner during the merchandizing and planning process rather than being optimized across all stores and the entire assortment of products.
While this process can improve product sales, it fails to fully optimize the product mix offered by retailers. Retail sales preferences can literally change overnight, while the traditional optimization process may occur seasonally or monthly, and even then not take into account the interactions between all the products and stores, for example. Moreover, it is almost impossible for a retail specialist to, e.g., consider shelf space restrictions for every store in a national retail chain.
The problem of optimizing the products offered for sale by a retailer is a generalization of what is commonly referred to as the “knapsack problem.” The knapsack problem is: Given a set of items with each item having two values (e.g., weight and price), and a constraint on one of the values (e.g., a knapsack can hold a finite weight), the goal of the “knapsack problem” is to maximize the sum of the other value subject to the constraint (i.e., what is the most valuable combination of items that can be stored in the knapsack without breaking it). There is presently no known polynomial time algorithm for exactly solving this class of problems, so people often rely on approximations. Currently known approximation approaches, e.g., allowing fractional allocations, tend not to work well with very large scale data sets and are typically not useful for obtaining answers in real time.
A need exists, therefore, for optimizing methods and apparatuses that overcome the above-mentioned disadvantages for the classical knapsack problem as well as the retail assortment optimization problem.